// Package _7__序列化二叉树 main
// @Title _7__序列化二叉树
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-11 15:04
// @Create  2022-02-11 15:04
package main

import (
	"fmt"
	"strconv"
	"strings"
)

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	var ans []string
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			ans = append(ans, "null")
			return
		}
		ans = append(ans, fmt.Sprintf("%d", root.Val))
		dfs(root.Left)
		dfs(root.Right)
	}
	dfs(root)
	return strings.Join(ans, "_")
}

func buildTree(list *[]string) *TreeNode {
	rootVal := (*list)[0]
	*list = (*list)[1:]
	if rootVal == "null" {
		return nil
	}
	val, _ := strconv.Atoi(rootVal)
	root := &TreeNode{Val: val}
	root.Left = buildTree(list)
	root.Right = buildTree(list)
	return root
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	ans := strings.Split(data, "_")
	if len(ans) == 0 {
		return nil
	}
	return buildTree(&ans)
}

func main() {
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
				Left: &TreeNode{
					Val:   4,
					Left:  nil,
					Right: nil,
				},
				Right: &TreeNode{
					Val:   4,
					Left:  nil,
					Right: nil,
				},
			},
			Right: &TreeNode{
				Val:   3,
				Left:  nil,
				Right: nil,
			},
		},
		Right: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val:   4,
				Left:  nil,
				Right: nil,
			},
			Right: nil,
		},
	}
	r := Constructor()
	ans := r.serialize(root)
	r.deserialize(ans)
}
